package main.new_2025.month_01;

import java.util.*;

/**
 * @Description:
 * todo 1926. 迷宫中离入口最近的出口
 * 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。
 * 同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
 * 每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。
 * 你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
 * 请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
 * @Author: Take-off
 * @Date: 1:00 PM 2024/2/27
 * @Param:
 * @return:
 **/
public class Solution0102 {

    //迷宫中离入口最近的出口,向上下左右枚举
    public int nearestExit(char[][] maze, int[] entrance) {
        //上下左右，到边界算跑，记录走过的路，不走重复路
        //上下左右
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        //边界
        int m = maze.length;
        int n = maze[0].length;
        int[] entrancePoint = entrance;
        //走过的路
        int[][] visited = new int[m][n];
        visited[entrancePoint[0]][entrancePoint[1]] = 1;
        //广度优先队列
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(entrancePoint);
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] currentPoint = queue.poll();
                // 检查当前点是否为出口
                if (isExit(currentPoint, m, n) && steps > 0) {
                    return steps;
                }
                // 向四个方向搜索
                for (int[] direction : directions) {
                    int[] nextPoint = {currentPoint[0] + direction[0], currentPoint[1] + direction[1]};
                    // 检查下一个点是否有效且未访问过
                    if (isValid(nextPoint, m, n,maze) && visited[nextPoint[0]][nextPoint[1]] == 0) {
                        visited[nextPoint[0]][nextPoint[1]] = 1;
                        queue.offer(nextPoint);
                    }
                }
            }
            steps++;
        }
        return -1;
    }

    // 判断一个点是否为出口
    private boolean isExit(int[] point, int m, int n) {
        int row = point[0];
        int col = point[1];
        return row == 0 || row == m - 1 || col == 0 || col == n - 1;
    }

    // 判断一个点是否有效
    private boolean isValid(int[] point, int m, int n,char[][] maze) {
        int row = point[0];
        int col = point[1];
        return row >= 0 && row < m && col >= 0 && col < n && maze[row][col] == '.';
    }

}